package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/3/24 12:38
 * @Version 1.0
 **/
public class BalancedBinaryTree {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else if (balance(root)) {
            return true;
        } else {
            return false;
        }
    }

    public boolean balance(TreeNode root) {
        if (Math.abs(getHeight(root.left,1)-getHeight(root.right,1)) < 2) {
            return balance(root.right) && balance(root.left);
        } else {
            return false;
        }
    }

    public int getHeight(TreeNode root,int height) {
        if (root == null) return height-1;
        int rHeight = getHeight(root.right,height+1);
        int lHeight = getHeight(root.left,height+1);
        return Math.max(rHeight,lHeight);
    }
}
